|
In computational complexity theory and analysis of algorithms, a number of metrics are defined describing the resources, such as time or space, that a machine needs to solve a particular problem. Interpreting these metrics meaningfully requires context, and this context is frequently implicit and depends on the field and the problem under consideration. This article describes a number of important pieces of context and how they affect metrics. == Definitions of variables == Metrics are usually described in terms of variables that are a function of the input. For example, the statement that insertion sort requires O(''n''2) comparisons is meaningless without defining ''n'', which in this case is the number of elements in the input list. Because many different contexts use the same letters for their variables, confusion can arise. For example, the complexity of primality tests and multiplication algorithms can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of binary digits (bits) in those integers. For example, if ''n'' is the integer being tested for primality, trial division can test it in Θ(n1/2) arithmetic operations; but if ''n'' is the number of bits in the integer being tested for primality, it requires Θ(2n/2) time. In the fields of cryptography and computational number theory, it is more typical to define the variable as the number of bits in the input integers. In the field of computational complexity theory, the input is usually specified as a binary string (or a string in some fixed alphabet), and the variable is usually the number of bits in this string. This measure depends on the specific encoding of the input, which must be specified. For example, if the input is an integer specified using unary coding, trial division will require only Θ(n1/2) arithmetic operations; but if the same input is specified in binary (or any larger base) the complexity rises to Θ(2n/2) operations, not because the algorithm is taking any additional time, but because the number of bits in the input ''n'' has become exponentially smaller. In the other direction, ''succinct circuits'' are compact representations of a limited class of graphs that occupy exponentially less space than ordinary representations like adjacency lists. Many graph algorithms on succinct circuits are EXPTIME-complete, whereas the same problems expressed with conventional representations are only P-complete, because the succinct circuit inputs have smaller encodings. Output-sensitive algorithms define their complexity not only in terms of their input but also their output. For example, Chan's algorithm can compute the convex hull of a set of points in O(''n'' log ''h'') time, where ''n'' is the number of points in the input and ''h'' is the number of points in the resulting convex hull, a subset of the input points. Because every input point ''might'' be in the convex hull, an analysis in terms of the input alone would yield the less precise O(''n'' log ''n'') time. The complexity of some algorithms depends not only on parameters of the input but also parameters of the machine the algorithm is being run on; as mentioned in #Metric being measured below, this is typical in analyzing algorithms that run on systems with fixed cache hierarchies, where the complexity may depend on parameters such as cache size and block size. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Context of computational complexity」の詳細全文を読む スポンサード リンク
|